package com.example;

/**
 * @Author loubobooo
 * @Description #2. 两数相加
 * @Date 2022/3/19
 */
public class AddTwoNumbers {

    /**
     * @return
     * @Author loubobooo
     * @Description 给出两个非空 的链表用来表示两个非负的整数。
     * 其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     * 您可以假设除了数字 0 之外，这两个数都不会以 0开头。
     * 此题不能用反转链表做
     * @Date 2022/3/19
     * @Param
     **/
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null || l2 != null || carry != 0) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            int sum = a + b + carry;
            carry = sum < 10 ? 0 : 1;
            sum = sum >= 10 ? sum - 10 : sum;

            ListNode temp = new ListNode(sum);
            // 接上temp
            cur.next = temp;
            // 指向下一个节点
            cur = cur.next;

            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        return dummyHead.next;
    }


    /**
     * @return
     * @Author loubobooo
     * @Description 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     * @Date 2022/3/19
     * @Param
     **/
    public static void main(String[] args) {
        int[] arr1 = {7,2,4,3};
        int[] arr2 = {5, 6, 4};
        ListNode node1 = new ListNode(-1);
        ListNode temp1 = node1;
        for (int i = 0; i < arr1.length; i++) {
            temp1.next = new ListNode(arr1[i]);
            temp1 = temp1.next;
        }
        ListNode node2 = new ListNode(-1);
        ListNode temp2 = node2;
        for (int i = 0; i < arr2.length; i++) {
            temp2.next = new ListNode(arr2[i]);
            temp2 = temp2.next;
        }
        AddTwoNumbers addTwoNumbers = new AddTwoNumbers();
        addTwoNumbers.addTwoNumbers(node1.next, node2.next);
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
